import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *车上最初有capacity个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）
 *
 * 给定整数capacity和一个数组 trips , trip[i] = [numPassengersi, fromi, toi]表示第 i 次旅行有numPassengersi乘客，接他们和放他们的位置分别是fromi和toi。这些位置是从汽车的初始位置向东的公里数。

 * 当且仅当你可以在所有给定的行程中接送所有乘客时，返回true，否则请返回 false。
 *https://leetcode.cn/problems/car-pooling/
 */
class CarPooling {
    public boolean carPooling(int[][] trips, int capacity) {
        int m=trips.length;
        int n=trips[0].length;
        PriorityQueue<int[]> min=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
//        for(int i=1;i<m;i++){
//            int j=0;
//            int[] tmp=trips[i];
//            for( j=i-1;j>=0;j--){
//               if(tmp[1]<trips[j][1]){
//                   trips[j+1]=trips[j];
//               } else{
//                   break;
//               }
//            }
//            trips[j+1]=tmp;
//        }这步可以用sort方法
        Arrays.sort(trips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for(int i=0;i<m;i++){
            capacity-=trips[i][0];
            while(!min.isEmpty()){
                int[] tmp=min.peek();
                if(tmp[1]<=trips[i][1]){
                    min.poll();
                    capacity+=tmp[0];
                }else{
                    break;
                }
            }
            if(capacity<0){
                return false;
            }
            min.offer(new int[]{trips[i][0],trips[i][2]});
        }
        return true;
    }
}